{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Missing Element in Sorted Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: missingElement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有序数组中的缺失元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一个按 <strong>升序</strong> 排列的整数数组 <code>nums</code> ，其中每个数字都 <strong>互不相同</strong> 。</p>\n",
    "\n",
    "<p>给你一个整数 <code>k</code> ，请你找出并返回从数组最左边开始的第 <code>k</code> 个缺失数字。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,7,9,10], k = 1\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>第一个缺失数字为 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,7,9,10], k = 3\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>缺失数字有 [5,6,8,...]，因此第三个缺失数字为 8 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,4], k = 3\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>缺失数字有 [3,5,6,7,...]，因此第三个缺失数字为 6 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= 10<sup>7</sup></code></li>\n",
    "\t<li><code>nums</code> 按 <strong>升序</strong> 排列，其中所有元素 <strong>互不相同</strong> 。</li>\n",
    "\t<li><code>1 <= k <= 10<sup>8</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以设计一个对数时间复杂度（即，<code>O(log(n))</code>）的解决方案吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [missing-element-in-sorted-array](https://leetcode.cn/problems/missing-element-in-sorted-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [missing-element-in-sorted-array](https://leetcode.cn/problems/missing-element-in-sorted-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,7,9,10]\\n1', '[4,7,9,10]\\n3', '[1,2,4]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0] + k\n",
    "\n",
    "        last_num = nums[0]\n",
    "        for nex_num in nums[1:]:\n",
    "            nums_btwn_last_and_next = nex_num - last_num - 1\n",
    "            if nums_btwn_last_and_next < k:\n",
    "                k -= nums_btwn_last_and_next\n",
    "            else:\n",
    "                return last_num + k\n",
    "            last_num = nex_num\n",
    "        return last_num + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        i = 0\n",
    "        cum_missing = 0\n",
    "        while i < len(nums) - 1:\n",
    "            cur_missing = nums[i+1] - nums[i] - 1\n",
    "            if cum_missing < k and cum_missing + cur_missing >= k:\n",
    "                delta = k - cum_missing\n",
    "                return nums[i] + delta\n",
    "            else:\n",
    "                cum_missing += cur_missing\n",
    "                i += 1\n",
    "        delta = k - cum_missing\n",
    "        return nums[-1] + delta\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        start = nums[0]\n",
    "        res = start + k\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] <= res:\n",
    "                res += 1\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "找到kth missing number 从nums中的第一个num到最后一个num中\n",
    "\n",
    "因为在Sorted array中找值，用binary search\n",
    "任意给一个index,我们要知道在他之前的missing number有什么\n",
    "找到一个位置，在他之前的missing number是>=k的，我们找到这个位置的前一个位置了，减去前一个位置的missing number, 然后从前一个位置累加计算出kth missing number\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        if not nums: return -1\n",
    "\n",
    "        def get_missing_counts(index):\n",
    "            return nums[index] - nums[0] - index\n",
    "            # index = 1, 7-4-1 = 2 (5, 6 missing)\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        # missing num 小于k\n",
    "        if get_missing_counts(n - 1) < k:\n",
    "            return nums[-1] + (k - get_missing_counts(n - 1))\n",
    "\n",
    "        left, right = 0, len(nums) - 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            # 如果在mid位置上，missing number小于k,我们要往右边找\n",
    "            if get_missing_counts(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        return nums[left - 1] + k - get_missing_counts(left - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        left, right = 0, len(nums) - 1\n",
    "\n",
    "        ret = self.cal(right, left, nums)\n",
    "        if ret < k:\n",
    "            return nums[-1] + k - ret\n",
    "        while left < right-1:\n",
    "\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            ret = self.cal(mid, left, nums)\n",
    "            if ret >= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "                k -= ret\n",
    "            print(left, right)\n",
    "        return nums[left]+k\n",
    "\n",
    "    \n",
    "    def cal(self, right, left, nums):\n",
    "        return nums[right] - nums[left] - (right - left)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0] + k\n",
    "        for i in range(1, n):\n",
    "            num_missing = nums[i] - nums[0] - i\n",
    "            if num_missing >= k:\n",
    "                return nums[i] - (num_missing - k + 1)\n",
    "        return nums[i] + (k - num_missing)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        i, j = 0, len(nums)-1\n",
    "        s = (nums[j] - nums[i]) - (j - i)\n",
    "        if s < k: return nums[j] + k - s\n",
    "        while i+1 < j:\n",
    "            mid = (i + j) // 2\n",
    "            s = (nums[mid] - nums[i]) - (mid - i)\n",
    "            if s >= k:\n",
    "                j = mid\n",
    "            else:\n",
    "                k = k - s\n",
    "                i = mid\n",
    "        return nums[i] + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        left, right = 0, len(nums)\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            missing = nums[mid] - nums[0] - mid\n",
    "\n",
    "            if missing < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return nums[0] + k + left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        t = nums[0] + k\n",
    "        l, r = 0, len(nums) - 1\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            sup = t + mid\n",
    "            if nums[mid] >= sup:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return t + r\n",
    "\n",
    "        \n",
    "         \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        start = nums[0]+1\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(1,n):\n",
    "            x = nums[i]\n",
    "            if x-start>=k:\n",
    "                return start+k-1\n",
    "            else:\n",
    "                k -= x-start\n",
    "                start = x+1\n",
    "        \n",
    "\n",
    "        return start+k-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        n = len(nums)\n",
    "        # 当前值减去首值减去坐标即位当前到开始确实的值的个数\n",
    "        missing = lambda x: nums[x] - nums[0] - x\n",
    "\n",
    "        if k > missing(n - 1):\n",
    "            return nums[-1] + k - missing(n - 1)\n",
    "\n",
    "        l, r = 0, n - 1\n",
    "\n",
    "        while l <= r:\n",
    "\n",
    "            mid = ( l + r ) // 2\n",
    "\n",
    "            if missing(mid) < k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        \n",
    "        return nums[l - 1] + k - missing(l - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        l=len(nums)\n",
    "        for i in range(1,l):\n",
    "            if nums[i]-nums[i-1]==1:\n",
    "                continue  \n",
    "            else:\n",
    "                if nums[i]-nums[i-1]<=k:\n",
    "                    k-=(nums[i]-nums[i-1]-1)\n",
    "                else:\n",
    "                    return nums[i-1]+k  \n",
    "        return nums[-1]+k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            diff = nums[i] - nums[i - 1] - 1\n",
    "            if diff >= k:\n",
    "                return nums[i - 1] + k\n",
    "            else:\n",
    "                k -= diff\n",
    "        return nums[n - 1] + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        l, r = 0, len(nums) - 1\n",
    "        mid = (l + r) // 2\n",
    "        while l < r:\n",
    "            if nums[mid + 1] - nums[l] >= mid + 1 - l + k:\n",
    "                r = mid\n",
    "            else:\n",
    "                k -= nums[mid + 1] - nums[l] + l - mid - 1\n",
    "                l = mid + 1\n",
    "            mid = (l + r) // 2\n",
    "        # l -= 1\n",
    "        ans = nums[l] + k\n",
    "        print(ans)\n",
    "        return nums[l] + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        s, e = 0, len(nums)-1\n",
    "        while s<=e:\n",
    "            m = s+(e-s)//2\n",
    "            miss = nums[m]-nums[0]-m\n",
    "            if miss>=k:\n",
    "                e = m-1\n",
    "            else:\n",
    "                s = m+1\n",
    "        return nums[e]+k-(nums[e]-nums[0]-e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        tmp, i = nums[0]+k,1\n",
    "        while i<len(nums) and nums[i]<=tmp:\n",
    "            tmp+=1\n",
    "            i+=1\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            miss = nums[i]-nums[i-1]-1\n",
    "            if miss>=k:\n",
    "                return nums[i-1]+k\n",
    "            k -= miss\n",
    "        return nums[-1]+k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        # prex_Sum=[0]\n",
    "        # for i in range(1,len(nums)):\n",
    "        #     prex_Sum.append(prex_Sum[i-1]+nums[i]-nums[i-1]-1)\n",
    "\n",
    "        prex_Sum=lambda idx:nums[idx]-nums[0]-idx\n",
    "\n",
    "        l,r=0,len(nums)-1\n",
    "        if prex_Sum(r)<k:\n",
    "            return k-prex_Sum(r)+nums[-1]\n",
    "\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if prex_Sum(mid)<k:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        return nums[l-1]+k-prex_Sum(l-1)\n",
    "        #tc: n(logn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        curvalue = nums[0]\n",
    "        curpoint = 0\n",
    "        if (nums[-1] - curvalue + 1 - len(nums)) < k:\n",
    "            return nums[-1] + (k - (nums[-1] - curvalue + 1 - len(nums)))\n",
    "        else:\n",
    "            while k > 0:\n",
    "                if nums[curpoint] == curvalue:\n",
    "                    curpoint += 1\n",
    "                    curvalue += 1\n",
    "                else:\n",
    "                    curvalue += 1\n",
    "                    k -= 1\n",
    "            return curvalue - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.append(nums[-1] + k + 1)\n",
    "        nums_new = [x - nums[0] - index for index, x in enumerate(nums)]\n",
    "        key = bisect.bisect_left(nums_new, k) - 1\n",
    "        if key <= 0:\n",
    "            return nums[0] + k\n",
    "        else:\n",
    "            return nums[0] + key + k\n",
    "\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        # if len(nums) == 2:\n",
    "        #     return nums[0] + k\n",
    "        range_ = nums[-1] - nums[0]\n",
    "        n = len(nums)\n",
    "        miss = range_ - n + 1\n",
    "        if k > miss:\n",
    "            return nums[-1] + k - miss\n",
    "        if k <= miss and n == 2:\n",
    "            return nums[0] + k\n",
    "        if len(nums) % 2 == 0:\n",
    "            idx_m = len(nums) // 2 - 1\n",
    "            left, right = len(nums) // 2, len(nums) // 2\n",
    "        else:\n",
    "            idx_m = len(nums) // 2\n",
    "            left, right = len(nums) // 2 + 1, len(nums) // 2\n",
    "        left_miss = nums[idx_m] - nums[0] + 1 - left\n",
    "        right_miss = miss - left_miss\n",
    "        if k <= left_miss:\n",
    "            return self.missingElement(nums[:idx_m+1], k)\n",
    "        else:\n",
    "            return self.missingElement(nums[idx_m:], k-left_miss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        def missing(nums: List[int], idx: int):\n",
    "            return nums[idx]-nums[0]-idx\n",
    "        n = len(nums)\n",
    "        if k>missing(nums, n-1):\n",
    "            return nums[n-1]+k-missing(nums, n-1)\n",
    "        left, right = 0, n-1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if(missing(nums, mid)<k):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return nums[left-1]+k-missing(nums, left-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        def helper(l,r):\n",
    "            return nums[r] - nums[l] -(r-l)\n",
    "\n",
    "        if k > helper(0, len(nums)-1):\n",
    "            return nums[-1] + k - helper(0, len(nums)-1)\n",
    "\n",
    "        l = 0\n",
    "        r = len(nums) - 1\n",
    "\n",
    "        while l < r-1:\n",
    "            m = (l + r) // 2\n",
    "            if helper(l, m) >= k:\n",
    "                r = m\n",
    "            else:\n",
    "                k -= helper(l, m)\n",
    "                l = m\n",
    "        return nums[l] + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        missing = lambda idx: nums[idx] - nums[0] - idx\n",
    "\n",
    "        n = len(nums)\n",
    "        if k > missing(n-1):\n",
    "            return nums[n - 1] + k - missing(n - 1)\n",
    "        \n",
    "        idx = 1\n",
    "        while missing(idx) < k:\n",
    "            idx += 1\n",
    "        return nums[idx - 1] + k - missing(idx - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        l, r = 0, len(nums) - 1\n",
    "        mid = (l + r) // 2\n",
    "        while l < r:\n",
    "            if nums[mid + 1] - nums[l] >= mid + 1 - l + k:\n",
    "                r = mid\n",
    "            else:\n",
    "                k -= nums[mid + 1] - nums[l] + l - mid - 1\n",
    "                l = mid + 1\n",
    "            mid = (l + r) // 2\n",
    "        # l -= 1\n",
    "        ans = nums[l] + k if k > 0 else nums[l] + k - 1\n",
    "        print(ans)\n",
    "        return nums[l] + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if i == n - 1: break\n",
    "            curInterval = nums[i + 1] - nums[i] - 1\n",
    "            if curInterval < k:\n",
    "                k = k - curInterval\n",
    "            else:\n",
    "                break\n",
    "        return nums[i] + k if i < n else nums[-1] + k\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        tmp = []\n",
    "        for i in range(1, len(nums)):\n",
    "            tmp.append(nums[i] - nums[i - 1] - 1)\n",
    "        if sum(tmp) < k:\n",
    "            return nums[-1] + (k - sum(tmp))\n",
    "        \n",
    "        flag = 0\n",
    "        index = 0\n",
    "        while flag < k:\n",
    "            flag += tmp[index]\n",
    "            index += 1\n",
    "        return nums[index-1] + (k - flag + tmp[index - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        length = len(nums)\n",
    "        left = 0\n",
    "        right = length - 1\n",
    "\n",
    "        if nums[right] - nums[left] - right <k:\n",
    "            return nums[left] + k + right\n",
    "\n",
    "        while left +1 <right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            slot = nums[mid] - nums[left] - mid + left\n",
    "\n",
    "            if slot < k:\n",
    "                left = mid \n",
    "                k -= slot\n",
    "            else:\n",
    "                right = mid\n",
    "        return nums[left] + k\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        length = len(nums)\n",
    "\n",
    "        for index in range(1, length):\n",
    "            loss = nums[index] - nums[index - 1] - 1\n",
    "\n",
    "            if loss >= k:\n",
    "                return nums[index - 1] + k\n",
    "            else:\n",
    "                k -= loss\n",
    "        return nums[length - 1] + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        left, right = 0, len(nums) - 1\n",
    "\n",
    "        delta = nums[right] - nums[left] - (right - left)\n",
    "        print('delta', delta)\n",
    "        if delta < k:\n",
    "            return nums[right] + k - delta\n",
    "        else:\n",
    "            while right - left > 1:\n",
    "                mid = left + (right - left) // 2\n",
    "\n",
    "                delta = nums[mid] - nums[left] - (mid - left)\n",
    "                \n",
    "                if delta >= k:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "                    k -= delta\n",
    "            \n",
    "            if right - left == 1:\n",
    "                return nums[left] + k\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        start = nums[0]\n",
    "        res = start + k\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] <= res:\n",
    "                res += 1\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        start = nums[0]\n",
    "        for n in nums:\n",
    "            if start == n:\n",
    "                start += 1\n",
    "                continue\n",
    "            diff = n - start\n",
    "            if k > diff:\n",
    "                k -= diff\n",
    "                start = n + 1\n",
    "                continue\n",
    "            return start + k - 1\n",
    "        return nums[-1] + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        n=0\n",
    "        l=len(nums)\n",
    "        res=[]\n",
    "        for i in range(1,l):\n",
    "            if nums[i]-nums[i-1]==1:\n",
    "                continue\n",
    "            else:\n",
    "                if k>nums[i]-nums[i-1]-1:\n",
    "                    k-=nums[i]-nums[i-1]-1\n",
    "                else:\n",
    "                    return nums[i-1]+k\n",
    "        return nums[-1]+k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        left, right = 0, len(nums) - 1\n",
    "\n",
    "        delta = nums[right] - nums[left] - (right - left)\n",
    "        print('delta', delta)\n",
    "        if delta < k:\n",
    "            return nums[right] + k - delta\n",
    "        else:\n",
    "            while right - left > 1:\n",
    "                mid = left + (right - left) // 2\n",
    "\n",
    "                delta = nums[mid] - nums[left] - (mid - left)\n",
    "                print('delta', delta, nums[mid], nums[left], 'k', k)\n",
    "                \n",
    "                if delta >= k:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "                    k -= delta\n",
    "            \n",
    "            print(left, right)\n",
    "            if right - left == 1:\n",
    "                return nums[left] + k\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        missing = lambda x: nums[x] - nums[0] - x\n",
    "\n",
    "        if missing(n - 1) < k:\n",
    "            return nums[-1] + k - missing(n - 1)\n",
    "\n",
    "\n",
    "        l, r = 0, n - 1\n",
    "\n",
    "        while l< r:\n",
    "\n",
    "            mid = ( l + r ) //2\n",
    "\n",
    "            if missing(mid) >= k:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return nums[l - 1] + k - missing(l - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        curvalue = nums[0]\n",
    "        curpoint = 0\n",
    "        if (nums[-1] - curvalue + 1 - len(nums)) < k:\n",
    "            return nums[-1] + (k - (nums[-1] - curvalue + 1 - len(nums)))\n",
    "        else:\n",
    "            while k > 0:\n",
    "                if nums[curpoint] == curvalue:\n",
    "                    curpoint += 1\n",
    "                    curvalue += 1\n",
    "                else:\n",
    "                    curvalue += 1\n",
    "                    k -= 1\n",
    "            return curvalue - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        # 找出最后一个缺失数字个数小于k个的位置，根据该位置直接计算得出结果\n",
    "        i, j = 0, len(nums) - 1\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            if nums[m] - (nums[0] + m) < k:\n",
    "                i = m + 1\n",
    "            else:\n",
    "                j = m - 1\n",
    "        return nums[0] + j + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        missing = lambda idx: nums[idx] - nums[0] - idx\n",
    "\n",
    "        n = len(nums)\n",
    "        if k > missing(n-1):\n",
    "            return nums[n - 1] + k - missing(n - 1)\n",
    "        \n",
    "        left = 0 \n",
    "        right = len(nums) - 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if missing(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return nums[left - 1] + k - missing(left - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        n = len(nums)\n",
    "        missing = lambda x: nums[x] - nums[0] - x\n",
    "\n",
    "        if k > missing(n - 1):\n",
    "            return nums[-1] + k - missing(n - 1)\n",
    "\n",
    "        l, r = 0, n - 1\n",
    "\n",
    "        while l <= r:\n",
    "\n",
    "            mid = ( l + r ) // 2\n",
    "\n",
    "            if missing(mid) < k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        \n",
    "        return nums[l - 1] + k - missing(l - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1: return nums[0] + k\n",
    "        a = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            dif = nums[i] - (a + 1)\n",
    "            a = nums[i]\n",
    "            if dif > 0:\n",
    "                k -= dif\n",
    "            if k == 0: return nums[i] - 1\n",
    "            elif k < 0: return nums[i] + k - 1\n",
    "\n",
    "        if k:\n",
    "            return nums[-1] + k\n",
    "        \n",
    "         \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        n, cnt = len(nums), 0\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            prev, cur = nums[i - 1], nums[i] if i <  n else inf\n",
    "            if prev + 1 != cur:\n",
    "                if cnt + cur - prev - 1 >= k:\n",
    "                    return prev + k - cnt\n",
    "                else:\n",
    "                    cnt += cur - prev - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        start = nums[0]\n",
    "        miss_cnt = 0\n",
    "        should_be = start + 1\n",
    "\n",
    "        for num in nums[1:]:\n",
    "            while num != should_be:\n",
    "                miss_cnt += 1\n",
    "                if miss_cnt == k:\n",
    "                    return should_be\n",
    "                should_be = should_be + 1\n",
    "            should_be = num + 1\n",
    "        \n",
    "        return nums[-1] + k - miss_cnt\n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        def missnum(start, num, i):\n",
    "            return num-start-i\n",
    "\n",
    "        n = len(nums)\n",
    "        start = nums[0]\n",
    "        l = 0\n",
    "        r = n-1\n",
    "\n",
    "        while l < r:\n",
    "            m = (l+r)//2\n",
    "            if missnum(start, nums[m], m) >= k:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m+1\n",
    "\n",
    "        if missnum(start, nums[l], l) < k:\n",
    "            return nums[l]+(k-missnum(start, nums[l], l))\n",
    "        else:\n",
    "            return nums[l-1]+(k-missnum(start, nums[l-1], l-1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        l, r = 0, len(nums) - 1\n",
    "\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            diff = nums[mid] - nums[l] - (mid - l)\n",
    "            if diff >= k:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "                k -= diff\n",
    "            \n",
    "        return nums[l] + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        l, r = 0, len(nums) - 1\n",
    "        mid = (l + r) // 2\n",
    "        while l < r:\n",
    "            if nums[mid] - nums[l] >= mid - l + k:\n",
    "                r = mid\n",
    "            else:\n",
    "                k -= nums[mid + 1] - nums[l] + l - mid - 1\n",
    "                l = mid + 1\n",
    "            mid = (l + r) // 2\n",
    "        # l -= 1\n",
    "        ans = nums[l] + k if k > 0 else nums[l] + k - 1\n",
    "        print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        # O(n)\n",
    "        # missingArray = []\n",
    "        # for i in range(nums[0], nums[0] + k + len(nums) + 1):\n",
    "        #     if i not in nums:\n",
    "        #         missingArray.append(i)\n",
    "        # return missingArray[k-1]\n",
    "\n",
    "        # O(logn)\n",
    "        # n :            0 1 2 3\n",
    "        # nums(n) :     [4,7,9,10]\n",
    "        # nums[0] + n : [4,5,6,7]\n",
    "        # 相减 ：        [0,2,3,3]\n",
    "        def findMiss(n):\n",
    "            return nums[n] - nums[0] - n\n",
    "\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if findMiss(mid) < k:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        if findMiss(right) < k:\n",
    "            return nums[right] + k - findMiss(right)\n",
    "        return nums[left] + k - findMiss(left)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        l, r = 0, len(nums)-1\n",
    "        t = self.cal(l, r, nums)\n",
    "        if k > t:\n",
    "            return nums[-1] + k - t\n",
    "\n",
    "        # left, right = 0, len(nums)-1\n",
    "        # # When left = right + 1, K must be in the middle of them\n",
    "        # while left < right - 1:\n",
    "        #     mid = (left +right) //2\n",
    "        #     leftBlankNum = self.cal(left, mid, nums)\n",
    "        #     if k <= leftBlankNum:\n",
    "        #         right = mid\n",
    "        #     else:\n",
    "        #         left = mid\n",
    "        #         k -= leftBlankNum\n",
    "        # return nums[left] + k\n",
    "\n",
    "        l, r = 0, len(nums) - 1\n",
    "        while l < r-1:\n",
    "            mid = (l+r) //2\n",
    "\n",
    "            m = self.cal(l, mid, nums)\n",
    "            if k <= m:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "                k -= m\n",
    "    \n",
    "        return nums[l] +k\n",
    "\n",
    "    def cal(self, left, right, nums):\n",
    "        return nums[right] - nums[left] - (right - left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(1,n):\n",
    "            loss = nums[i] - nums[i-1] - 1\n",
    "            if loss >= k:\n",
    "                return nums[i-1] + k\n",
    "            else:\n",
    "                k -= loss\n",
    "        return nums[n-1] + k\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        missing = lambda i: nums[i] - nums[0] - i \n",
    "\n",
    "        if k > missing(n - 1):\n",
    "            return nums[-1] + k - missing(n - 1)\n",
    "        \n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if missing(mid) < k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return nums[r - 1] + k - missing(r - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            # [4,7,9,10]\n",
    "            prev, cur = nums[i - 1], nums[i]\n",
    "            # 4, 7\n",
    "            if prev + 1 != cur:\n",
    "                if cnt + cur - prev - 1 >= k:\n",
    "                    return prev + k - cnt\n",
    "                else:\n",
    "                    cnt += cur - prev - 1\n",
    "        return nums[-1] + k - cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        # O(n)\n",
    "        # missingArray = []\n",
    "        # for i in range(nums[0], nums[0] + k + len(nums) + 1):\n",
    "        #     if i not in nums:\n",
    "        #         missingArray.append(i)\n",
    "        # return missingArray[k-1]\n",
    "\n",
    "        # O(logn)\n",
    "        # n :            0 1 2 3\n",
    "        # nums(n) :     [4,7,9,10]\n",
    "        # nums[0] + n : [4,5,6,7]\n",
    "        # 相减 ：        [0,2,3,3]\n",
    "        def findMiss(n):\n",
    "            return nums[n] - nums[0] - n\n",
    "\n",
    "        left, right = 0, len(nums) - 1\n",
    "        if k > findMiss(right):\n",
    "            return nums[-1] + k - findMiss(right)\n",
    "\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if findMiss(mid) < k:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        if findMiss(right) < k:\n",
    "            return nums[right] + k - findMiss(right)\n",
    "        return nums[left] + k - findMiss(left)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        # Return how many numbers are missing until nums[idx]\n",
    "        missing = lambda idx: nums[idx] - nums[0] - idx\n",
    "            \n",
    "        n = len(nums)\n",
    "        # If kth missing number is larger than \n",
    "        # the last element of the array\n",
    "        if k > missing(n - 1):\n",
    "            return nums[-1] + k - missing(n - 1) \n",
    "        \n",
    "        left, right = 0, n - 1\n",
    "        # find left = right index such that \n",
    "        # missing(left - 1) < k <= missing(left)\n",
    "        while left != right:\n",
    "            pivot = left + (right - left) // 2\n",
    "            \n",
    "            if missing(pivot) < k:\n",
    "                left = pivot + 1\n",
    "            else:\n",
    "                right = pivot \n",
    "        \n",
    "        # kth missing number is larger than nums[left - 1]\n",
    "        # and smaller than nums[left]\n",
    "        return nums[left - 1] + k - missing(left - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        # Return how many numbers are missing until nums[idx]\n",
    "        missing = lambda idx: nums[idx] - nums[0] - idx\n",
    "                \n",
    "        n = len(nums)\n",
    "        # If kth missing number is larger than \n",
    "        # the last element of the array\n",
    "        if k > missing(n - 1):\n",
    "            return nums[-1] + k - missing(n - 1) \n",
    "\n",
    "        idx = 1\n",
    "        # find idx such that \n",
    "        # missing(idx - 1) < k <= missing(idx)\n",
    "        while missing(idx) < k:\n",
    "            idx += 1\n",
    "\n",
    "        # kth missing number is larger than nums[idx - 1]\n",
    "        # and smaller than nums[idx]\n",
    "        return nums[idx - 1] + k - missing(idx - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        curvalue = nums[0]\n",
    "        curpoint = 0\n",
    "        if (nums[-1] - curvalue + 1 - len(nums)) < k:\n",
    "            return nums[-1] + (k - (nums[-1] - curvalue + 1 - len(nums)))\n",
    "        else:\n",
    "            while k > 0:\n",
    "                if nums[min(curpoint, len(nums)-1)] == curvalue:\n",
    "                    curpoint += 1\n",
    "                    curvalue += 1\n",
    "                else:\n",
    "                    curvalue += 1\n",
    "                    k -= 1\n",
    "            return curvalue - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        prex_Sum=[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            prex_Sum.append(prex_Sum[i-1]+nums[i]-nums[i-1]-1)\n",
    "        l,r=0,len(nums)-1\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if prex_Sum[mid]<k:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        if prex_Sum[l]<k:\n",
    "            return k-prex_Sum[l]+nums[l]\n",
    "        return nums[l]-(prex_Sum[l]-k)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        missing = [nums[i] - nums[0] - i for i in range(n)]\n",
    "        if k > missing[n-1]:\n",
    "            return nums[-1] + k - missing[n-1]\n",
    "        idx = 1\n",
    "        while missing[idx] < k:\n",
    "            idx += 1\n",
    "        return nums[idx-1] + k - missing[idx-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingElement(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        missing = [nums[i] - nums[0] - i for i in range(n)]\n",
    "        if k > missing[n-1]:\n",
    "            return nums[-1] + k - missing[n-1]\n",
    "        idx = 1\n",
    "        left, right = 0, n-1\n",
    "        while left != right:\n",
    "            mid = (left + right) >> 1\n",
    "            if missing[mid] < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return nums[left-1] + k - missing[left-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
